You are given a rectangular cake of size h x w and two arrays of integers horizontalCuts and verticalCuts where:
horizontalCuts[i]is the distance from the top of the rectangular cake to theithhorizontal cut and similarly, andverticalCuts[j]is the distance from the left of the rectangular cake to thejthvertical cut.
Return the maximum area of a piece of cake after you cut at each horizontal and vertical position provided in the arrays horizontalCuts and verticalCuts. Since the answer can be a large number, return this modulo 109 + 7.
Example 1:
Input: h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3] Output: 4 Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green piece of cake has the maximum area.
Example 2:
Input: h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1] Output: 6 Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green and yellow pieces of cake have the maximum area.
Example 3:
Input: h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3] Output: 9
Constraints:
2 <= h, w <= 1091 <= horizontalCuts.length <= min(h - 1, 105)1 <= verticalCuts.length <= min(w - 1, 105)1 <= horizontalCuts[i] < h1 <= verticalCuts[i] < w- All the elements in
horizontalCutsare distinct. - All the elements in
verticalCutsare distinct.
Average Rating: 5.00 (17 votes)
Solution
Overview
Calculating the area of every possible piece of cake can get out of hand very quickly. In the first example alone, there are already 12 pieces of cake, and our input can have up to 100,000 vertical and horizontal cuts. We need a smarter way to find the area of the largest piece of cake.
The key insight to solve this problem is that not all of the pairs of horizontal and vertical cuts matter. Let's take a step back - the area of a cake piece is defined by width * height. If we were to consider only the horizontal cuts, then we would end up with many pieces of cake with width = w and varying heights. For each new piece, making a vertical cut will change the width, but not the height.
Let's use the first test case in the problem description as an example. If we were to only apply the horizontal cuts [1, 2, 4], we will end up with 4 pieces of cake, all with width = 4. Take the piece of cake with height = 2 between the cuts at 2 and 4, and make any vertical cut you want - notice that the height will always be 2. The same logic can be applied when considering the vertical cuts first - we will have many pieces of cake with height = h and varying widths.
Therefore, we know the largest piece of cake must have a height equal to the tallest height after applying only the horizontal cuts, and it will have a width equal to the widest width after applying only the vertical cuts.
Approach: Sort
Intuition
As mentioned above, we can find the max height and the max width separately. Our final answer will be maxHeight * maxWidth. Each height and width is defined by the distance between 2 cuts. In the first example, the max height of 2 is defined by the distance between cuts 2 and 4 (4 - 2 = 2). To find all heights and widths, we must first sort our inputs horizontalCuts and verticalCuts. This will ensure that all of the cuts that are beside each other on the cake are also beside each other in the array. Then, we can iterate through the sorted inputs one at a time and find each height or width by simply taking the difference between two adjacent cuts.
One thing to be careful about is the edges. For cuts in the middle, the distance is defined by the difference between two cuts. However, for the edges, they are defined by the cake's dimensions.
- The top-most cut's height will be equal to
horizontalCuts[0], while the bottom-most cut's height will be equal toh - horizontalCuts[horizontalCuts.length - 1]. - The left-most cut's width will be equal to
verticalCuts[0], while the right-most cut's width will be equal tow - verticalCuts[verticalCuts.length - 1].
Algorithm
-
Sort both
horizontalCutsandverticalCutsin ascending order. -
Initialize a variable
maxHeightas the larger of the top and bottom edge:maxHeight = max(horizontalCuts[0], h - horizontalCuts[horizontalCuts.length - 1]). -
Iterate through
horizontalCutsstarting from index 1 (skip the 0th index since it represents the edge cut, which we accounted for in the previous step). At each iteration, find the height defined by the ith cut and the nearest cut above,horizontalCuts[i] - horizontalCuts[i - 1]. UpdatemaxHeightif necessary. -
Initialize a variable
maxWidthas the larger of the left and right edge:maxWidth = max(verticalCuts[0], w - verticalCuts[verticalCuts.length - 1]). -
Iterate through
verticalCutsstarting from index 1. At each iteration, find the width defined by the ith cut and the nearest cut to the left,verticalCuts[i] - verticalCuts[i - 1]. UpdatemaxWidthif necessary. -
Our maximum area is
maxHeight * maxWidth. Don't forget the modulo 109+7, and depending on what language you're using, be careful of overflow. Return the maximum area.
Implementation
Complexity Analysis
Given N as the length of horizontalCuts and M as the length of verticalCuts,
-
Time complexity: O(N⋅log(N)+M⋅log(M))
Sorting an array of length n costs n⋅logn time. We need to sort both
horizontalCutsandverticalCuts, which is why both are present in the time complexity. Although we also iterate through both arrays, which costs O(N) and O(M) time, these iterations are not as expensive as the sorting, and by the rules of Big O, do not get included in the final time complexity. -
Space complexity: O(1)
Regardless of the input size, we only ever need to use 2 variables:
maxHeightandmaxWidth.
June 3, 2021 7:59 PM
It is possible to do this in O(n) actually. This problem is essentially the same as https://leetcode.com/problems/maximum-gap/ which has an O(n) bucket sort solution.
Runtime fluctuates a lot but this solution beats 100% time (28ms) using the maximum gap solution as a subroutine.
int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {
auto [maxHGap, minHCut, maxHCut] = maxGapAndExtrema(horizontalCuts);
auto [maxVGap, minVCut, maxVCut] = maxGapAndExtrema(verticalCuts);
int maxH, maxV;
if (maxHGap != -1)
maxH = max({minHCut, h - maxHCut, maxHGap});
else
maxH = max(horizontalCuts.front(), h - horizontalCuts.back());
if (maxVGap != -1)
maxV = max({minVCut, w - maxVCut, maxVGap});
else
maxV = max(verticalCuts.front(), w - verticalCuts.back());
const int m = 1000000007;
return (static_cast<long>((maxH%m)) * (maxV%m) %m);
}
tuple<int, int, int> maxGapAndExtrema(vector<int>& nums) {
// Sentinel
if (nums.size() <= 1)
return {-1, -1, -1};
int minVal = INT_MAX, maxVal = INT_MIN;
for (int num : nums) {
minVal = min(minVal, num);
maxVal = max(maxVal, num);
}
assert(minVal != maxVal);
const int size = nums.size()-1;
const int smallestPossibleGap = static_cast<int>(
ceil(static_cast<double>(maxVal - minVal) / size)
);
int* __restrict__ minBuckets = new int[size];
fill(minBuckets, minBuckets+size, INT_MAX);
int* __restrict__ maxBuckets = new int[size];
fill(maxBuckets, maxBuckets+size, INT_MIN);
for (int num : nums) {
if (num == minVal || num == maxVal)
continue;
int idx = (num - minVal) / smallestPossibleGap;
minBuckets[idx] = min(minBuckets[idx], num);
maxBuckets[idx] = max(maxBuckets[idx], num);
}
int maxGap = INT_MIN;
int prev = minVal;
for (int i=0; i<nums.size()-1; ++i) {
if (minBuckets[i] == INT_MAX && maxBuckets[i] == INT_MIN)
continue;
maxGap = max(maxGap, minBuckets[i] - prev);
prev = maxBuckets[i];
}
delete[] minBuckets;
delete[] maxBuckets;
return { max(maxGap, maxVal - prev), minVal, maxVal };
}
Pretty well written article. This is a good lesson in clarifying requirements during an interview (needing to sort the arrays).
June 3, 2021 8:02 PM
A dangerous mistake I made is missed the boundary of those numbers and used int instead of long for the max value.. post here to remind myself
Shouldn't this be a Easy? Maybe I am missing something, but what makes this problem a Medium?
FYI, long is 8 bits size and int is 4 bits size, so if I use int for the maxHeight and maxWidth, it will be an overflow and truncated
June 4, 2021 10:55 AM
The operation on the cuts (vertical or horizontal) is the same: find the biggest cut, so the code can be refactored to reuse/reduce number of lines of code :
class Solution:
def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
result = [0,0]
for idx, items in enumerate([(horizontalCuts,h),(verticalCuts,w)]):
cuts,max_cut = items
cuts.append(0)
cuts.append(max_cut)
cuts.sort()
for i in range(len(cuts)-1):
result[idx] = max(result[idx], cuts[i+1]-cuts[i])
return result[0]*result[1] %(10**9 + 7)
Further more he code can be simplified by extracting the max_cut computation in a stand alone function.
There are magical lines in the >99.5% solution in Python. May I ask if anyone knows why?
if h == 1000000000:
return 755332975
Why maxDiff is not calculated with leftMost or upperMost condition? i.e. maxHeight = Math.max(maxHeight, horizontalCuts[i] - 0); and maxWidth = Math.max(maxWidth, verticalCuts[i] - 0);
Cannot understand why this fails the final test case . The maxColumn and MaxRow are correctly returned yet the final modulo calculation does not return the result
Arrays.sort(horizontalCuts);
Arrays.sort(verticalCuts);
int[] modifiedHorizontalCuts = new int[horizontalCuts.length+2];
int[] modifiedVerticalCuts = new int[verticalCuts.length+2];
for(int i = 0;i<modifiedHorizontalCuts.length;i++){
if(i==0) {
modifiedHorizontalCuts[i] = 0;
continue;
}
if(i==modifiedHorizontalCuts.length-1) {
modifiedHorizontalCuts[i] = h;
continue;
}
modifiedHorizontalCuts[i] = horizontalCuts[i-1];
}
for(int i = 0;i<modifiedVerticalCuts.length;i++){
if(i==0) {
modifiedVerticalCuts[i] = 0;
continue;
}
if(i==modifiedVerticalCuts.length-1) {
modifiedVerticalCuts[i] = w;
continue;
}
modifiedVerticalCuts[i] = verticalCuts[i-1];
}
int maxRow = 0;
for(int i=1;i<modifiedHorizontalCuts.length;i++){
maxRow = Math.max(maxRow,modifiedHorizontalCuts[i]-modifiedHorizontalCuts[i-1]);
}
int maxColumn = 0;
for(int i=1;i<modifiedVerticalCuts.length;i++){
maxColumn = Math.max(maxColumn,modifiedVerticalCuts[i]-modifiedVerticalCuts[i-1]);
}
// if(h==1000000000)
// System.out.println("Max Column "+maxColumn+" Max Row"+maxRow);
//return (int) ( ( maxColumn * maxRow ) % (1e9 + 7) );
return (int) ((maxColumn * maxRow) % (1e9 + 7));`Why does this fail for the final Testcase? Can anyone please suggest?
class Solution {
public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
Arrays.sort(horizontalCuts);
Arrays.sort(verticalCuts);
int largestHorizontal = getLargestPiece(horizontalCuts, h);
int largestVertical = getLargestPiece(verticalCuts, w);
return (int) ((largestHorizontal * largestVertical) % 1000000007);
}
private int getLargestPiece(int[] cuts, int total){
int prevCut = 0;
int largestPiece = 0;
for(int cut : cuts){
int currentPiece = cut - prevCut;
largestPiece = Math.max(largestPiece, currentPiece);
prevCut = cut;
}
largestPiece = Math.max(largestPiece, total - prevCut);
return largestPiece;
}
}
Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 06/03/2021 12:55 | Accepted | 84 ms | 32.1 MB | cpp |
| 05/31/2020 08:24 | Accepted | 356 ms | 32.2 MB | cpp |
| 05/31/2020 08:15 | Runtime Error | N/A | N/A | cpp |
| 05/31/2020 08:14 | Runtime Error | N/A | N/A | cpp |
xxxxxxxxxxclass Solution {public: int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) { }};